package template

import "fmt"

/*参考:https://studygolang.com/articles/18575
一、什么是位图
	通过一个bit位来表示数据的一个状态，例如一个bit为1则表示一个数存在，为0则表示不存在(位图实际上可以看成是hash表的一种变形)

二、位图的作用
	1.大量数据去重
	2.数据排序(类似于桶排序)

三、位图的实现
	一个bit位代表一个数据，例如第一个bit代表数字0，第二个bit代表数据1，第n个bit代表数字n-1；
	那如果需要存放数字n，该怎么办？？？
	golang中最小的类型为byte类型，即8个bit，可以表示8个数，那么假设最大的数为max，则需要的内存为max%8+1(对应位运算: max>>3+1),因为第一byte最多
	只能存储到数字7，数字8需要第二个byte的第一个bit来存储（因此需要+1）



*/

type BitMap struct {
	bits []byte
	max  int
}

// NewBitMap 构造函数,返回一个BitMap类型实例
func NewBitMap(max int) *BitMap {
	// max>>3+1就是max%8+1
	bits := make([]byte, max>>3+1)
	return &BitMap{bits: bits, max: max}
}

// Add 存放数字x, 先求出x对应的bits切片的索引index,然后再找到x在bits[index]这一个byte内对应的bit位
// 由于每一个数字只对应一个bit位,而一个byte中可以存储8个bit位,x & 0x07 求出x在bits[index]这一byte中位于第几个bit位
func (b *BitMap) Add(x int) {
	index := x >> 3
	// 求出x在bits[index]这一byte中位于第几个bit位(最开始的一个bit位为第0个bit位)
	pos := x & 0x07
	// 1<<pos 表示将第pos个bit位置为1
	// |= 是为了保留bits[index]中已置1的bit位
	b.bits[index] |= 1 << pos
}

// IsExist 判断一个数x是否存在在位图中
func (b *BitMap) IsExist(x int) bool {
	index := x >> 3
	pos := x & 0x07
	// 这里不能写成 b.bits[index] & (1 << pos) == 1,因为1<<pos得到的结果不一定是1
	return b.bits[index]&(1<<pos) != 0
}

// Remove 从位图中删除x
func (b *BitMap) Remove(x int) {
	index := x >> 3
	pos := index & 0x07
	// 按位置0, c = a &^ b  => 如果b中某一个为1,则c中对应该位要置为0,如果b中某一位为0,则c中该位等于a中的这一位
	b.bits[index] = b.bits[index] &^ (1 << pos)
}

// Max 返回位图中的最大数
func (b *BitMap) Max() int {
	return b.max
}

// String() 返回位图的字符串表示
// 注意,如果String()中打印的是接收者b,则会导致递归调用,因为默认fmt.Println(b)就是会调用b的String()方法,如果再在String()方法中
// 调用fmt.Println(b)则会导致递归调用,最终报错
//
// 但是在String()方法中打印b的字段,则没有问题
func (b *BitMap) String() string {
	return fmt.Sprint(b.bits)
}
